/**********************************************************

@description:
*File Name:graph.c
*Author: ydx
*mail: yudongxiang93@163.com
*Create Time: Wed 30 Apr 2025 10:53:12 PM CST
**********************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
//vexs not gothrough, the arc is MAX
//vexs gothrough with itself, the arc is 0
//
#define MAX 32767
typedef struct graph{
	char *vexs;
	int **arcs;
	int vex_num,arc_num;
}graph;

typedef struct snode{
	int data;
	struct snode* next;
}snode;
int isEmpty(snode* s){
	return s->data<=0;
}
void push(snode* s,int data){
	snode *n=(snode*)malloc(sizeof(snode));
	assert(n);
	n->data=data;
	n->next=s->next;
	s->next=n;
	s->data++;
}
snode* pop(snode* s){
	snode* n=s->next;
	if(n){
		s->next=s->next->next;
		s->data--;
		n->next=NULL;
	}
	return n;
}
snode* init_stack(){
	snode *s=(snode*)malloc(sizeof(snode));
	assert(s);
	s->data=0;
	s->next=NULL;
	return s;
}

void print_arr(int *arr,int len,char* name){
	printf("%s:\n",name);
	for(int i=0;i<len;i++){
		printf("%4d ",arr[i]);
	}
	printf("\n");
}
void print_aarr(int **arr,int leni,int lenj,char* name){
	printf("%s:\n",name);
	for(int i=0;i<leni;i++){
		for(int j=0;j<lenj;j++){
			printf("%4d ",arr[i][j]);
		}
		printf("\n");
	}
}
int* find_in_degrees(graph* g){
	int* indegress=(int*)malloc(sizeof(int)*g->vex_num);
	memset(indegress,0,g->vex_num*sizeof(int));
	for(int i=0;i<g->vex_num;i++){
		for(int j=0;j<g->vex_num;j++){
			if(g->arcs[i][j]){
				indegress[j]++;
			}
		}
	}
	return indegress;
}
void topological_sort(graph* g){
	int index=0;
	int* res=(int*)malloc(sizeof(int)*g->vex_num);
	memset(res,0,g->vex_num*sizeof(int));
	int* indegress=find_in_degrees(g);
	print_arr(indegress,g->vex_num,"indegress:");
	snode* s=init_stack();
	for(int i=0;i<g->vex_num;i++){
		if(!indegress[i]){
			push(s,i);
		}
	}
	while(!isEmpty(s)){
		snode* n=pop(s);
		res[index++]=n->data;
		for(int i=0;i<g->vex_num;i++){
			if(g->arcs[n->data][i]){
				indegress[i]=indegress[i]-1;
				if(indegress[i]==0)
					push(s,i);
			}
		}
	}
	print_arr(res,g->vex_num,"topresult:");
}
graph * init_graph(int vex_num){
	graph *g=(graph*)malloc(sizeof(graph));
	g->vexs=(char*)malloc(sizeof(char)*vex_num);
	g->arcs=(int**)malloc(sizeof(int*)*vex_num);
	for(int i=0;i<vex_num;i++){
		g->arcs[i]=(int*)malloc(sizeof(int)*vex_num);
	}
	g->vex_num=vex_num;
	g->arc_num=0;
	return g;
}
void createGraph(graph *g,char *vexs,int* arcs){
	for(int i=0;i<g->vex_num;i++){
		g->vexs[i]=vexs[i];
		for(int j=0;j<g->vex_num;j++){
			g->arcs[i][j]=*(arcs+i*g->vex_num+j);
			if(g->arcs[i][j] != 0){
				g->arc_num++;
			}
		}
	}
	g->arc_num/=2;
}
void dfs(graph *g,int* visited,int index){
	printf("%c\t",g->vexs[index]);
	visited[index]=1;
	for(int i=0;i<g->vex_num;i++){
		if(g->arcs[index][i] == 1 && !visited[i]){
			dfs(g,visited,i);
		}
	}
}

int main(){
	graph* g=init_graph(6);
	int arcs[36]={
		0,1,1,1,0,0,
		0,0,0,0,0,0,
		0,1,0,0,1,0,
		0,0,0,0,1,0,
		0,0,0,0,0,0,
		0,0,0,1,1,0,
	};
	createGraph(g,"123456",arcs);

	printf("dfs:");
	int *visited=(int*)malloc(sizeof(int)*g->vex_num);
	memset(visited,0,g->vex_num*sizeof(int));
	dfs(g,visited,0);
	printf("\n");
	topological_sort(g);
	
}
